COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00013 00003	.skip 2
C00014 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.EVERY HEADING(Flow Chart Functions,%7Draft%1,{page})
.CB THE BLOB FUNCTIONS OF FLOW CHARTS


	When one  studies programs organized  as flow charts,  one is
inclined to prefer flow charts with a single entry and a single exit.
However, the operations of building flow charts from parts inevitably
involve flow charts with multiple entries and multiple exits.

	Our  approach  is  to  characterize flow  charts  by  certain
functions, called %2blob functions%1,
and show how to get  the functions characterizing new flow
charts from those characterizing  the flow charts from which  the new
ones are formed.   This is in contrast with  the approach of Ianov as
described in (Ianov 1959)  and (Rutledge 1964) who work directly
with the flow charts.   Our reason is  that
mathematics  provides  us   with  powerful  tools   for  manipulating
functions,  and, moreover, facts  about flow charts  must be combined
with other mathematical facts which are most conveniently decribed in
terms of functions, predicates and sets.
.SKIP 10
.once center
Figure 1

.bb "#. Blob functions"

	Figure 1a represents a flow chart or %2blob%1 ⊗c whose inner
workings we do not wish to specify, but whose behavior we wish to
characterize by functions.  The arrows into the ⊗blob represent paths
along which control enters the flow chart (called entries), and the arrows
out represent paths by which control leaves it (called ⊗exits).  Let
⊗En(c) be the set of entries of ⊗c, and let ⊗Ex(c) be its set of exits.
Let ⊗x represent the state vector, i.e.  the collection of assignments of
values to the variables occurring in the program.  We define predicates
%2p%4ij%2(x,c)%1 where ⊗i ranges over ⊗En(c) and ⊗j ranges over %2Ex(c)%1,
and functions %2s%4i%1⊗(x,c) where ⊗i again ranges over ⊗En(c) as follows:

	(i) %2p%4ij%1⊗(x,c) is  true if and  only if entering the  flow
chart ⊗c  at entry ⊗i  with initial state  ⊗x results in  leaving the
flow chart at exit %2j%1.

	(ii) %2s%4i%1⊗(x,c) is the value of the state at exit from  the
flow chart when it is entered at ⊗i with initial state ⊗x.  Note that
the %2s%4i%1's are
partial functions, because the program may never exit.

	Obviously the predicates %2p%4ij%1 and the functions %2s%4i%1
characterize the flow chart ⊗c, because if one knows these, one knows
where the program  will exit and what  the new state will  be for any
entrance into the flow chart.

	If  we suppose that the flow  chart is ultimately constructed
out of elementary compute blocks and elementary  decision blocks
as in Figure 1b, one
needs to show how to write the %2p%1's and %2s%1's for these elements
and then  how to  get the  %2p%1's and  %2s%1's for  a combination  of
blocks from  those of  its  parts.   The first  part is  trivial.   A
compute block  has just one entry and one exit,  so there is just one
⊗p and it is identically  true, and there is  just one ⊗s, and it  is
just the  function of state computed  by the block.   A decision block
has one  entry and two exits and the one ⊗p is just the predicate for
the YES decision and the other is the predicate  for the NO decision.
There is one ⊗s, and it is the identity function.

.skip to column 1
	We introduce the following operations that give new charts from
old ones:
.skip 20
.once center
Figure 2

	(i) Suppression of an entry %2i%40%1  from a chart ⊗c
(see Figure 2a).   This
gives a new chart  %2suppress(c,i%40%2)%1 with one fewer entry,  and whose
%2p%1's and %2s%1's  are the same as before except that the subscript
%2i%40%1 is omitted.

	(ii) Adjoining two charts ⊗c1 and  ⊗c2 side by side (see Figure
2b).  Call  the
new  chart %2adjoin(c1,c2)%1.   We  have %2En(adjoin(c1,c2))
 = En(c1) ∪ En(c2)%1,  and
%2Ex(adjoin(c1,c2)) = Ex(c1) ∪ Ex(c2)%1.  Moreover, we have

!!a1:	%2p%4ij%2(x,adjoin(c1,c2)) = qif i ε c1 qthen (qif j ε c1
qthen p%4ij%2(x,c1) qelse %3false%2)  qelse (qif j ε c1  qthen %3false%2
qelse p%4ij%2(x,c2))%1,

and

!!a2:	%2s%4i%2(x,adjoin(c1,c2))  =  qif  i  ε c1  qthen  s%4i%2(x,c1)
qelse s%4i%2(x,c2)%1.

Both of these are trivial operations but the next is not.

	(iii) Connecting  the exit  ⊗m  to the  entry  ⊗n 
giving a  new chart  %2loop(c,m,n)%1 with  one fewer  exit (see Figure 2c).
The new %2p%1's and %2s%1's are defined by the recursion equations

!!a3:	%2p%4ij%2(x,loop(c,m,n)) ← p%4ij%2(x,c) ∨ (p%4im%2(x,c) ∧
p%4nj%2(s%4i%2(x,c),loop(c,m,n)))%1

and

!!a4:	%2s%4i%2(x,loop(c,m,n)) ← qif ¬p%4im%2(x,c) qthen
s%4i%2(x,c) qelse s%4n%2(s%4i%2(x,c),loop(c,m,n))%1.

	A little contemplation will show that this recursive process
captures our intuitive notion of what happens when an exit is connected
to an entry.

	It is evident that any flow chart can be built from
elementary compute blocks and tests by these operations, and furthermore
any two flow charts can be glued together using these operations.

	An objective worth undertaking is to show that any two equivalent
flow charts can be proved equivalent by the theory of recursively
defined functions from these definitions.  This would be the analog
of Ianov's theorem and ought to be based on a decision procedure for
recursions (possibly restricted to iterative form) where there is only
one variable.
It would have the advantage over the Ianov theory that it is simply
the theory of recursion equations applied to this case rather than
an ad hoc confection.

	I don't know such a decision procedure, nor has there been
formulated a theory of recursion equations that is proved complete
for this case.

Note of February 19, 1977:

	The recursion involved when an exit is connected to an entry
can be represented by a %2functional equation%1 and a %2minimization
schema%1 as discussed in (McCarthy 1977).

	If two exits of a chart are connected to two entries, this
can be done in two different orders - thus giving rise to two sets
of recursions for the new chart.  Moreover, a third set of recursions
can be obtained by doing the connections simultaneously.  It should
be possible to show from the %2functional equations%1 and %2minimization
schemas%1 of these recursions that the same funtions are obtained.
.skip 2
.bb REFERENCES

%3Ianov, Y.I.%1 (1960): "The Logical Schemes of Algorithms", in %2
Problems of Cybernetics%1, vol.1, pp. 82-140, Pergamon Press, New York
(English Translation).

%3Rutledge, J.D.%1 (1964): "On Ianov's Program Schemata", %2J. ACM%1,
%311%1(1): 1-9 (January).
.skip 2
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of
BLOB[W76,JMC]
PUBbed at {time} on {date}.%1